package com.dynamicprogram;

import java.util.*;

public class Solution95 {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> pre = new ArrayList<>();
        pre.add(null);
        for (int i = 1; i <= n; i++) {
            List<TreeNode> cur = new ArrayList<>();
            for (TreeNode root : pre) {
                TreeNode insert = new TreeNode(i);
                insert.left = root;
                cur.add(insert);
                for (int j = 0; j < i; j++) {
                    TreeNode newRoot = clone(root);
                    TreeNode right = newRoot;
                    for (int k = 0; k < j; k++) {
                        if (right == null) break;
                        right = right.right;
                    }
                    if (right == null) break;
                    TreeNode tmp = right.right;
                    insert = new TreeNode(i);
                    right.right = insert;
                    insert.left = tmp;
                    cur.add(newRoot);
                }
            }
            pre = cur;
        }
        return pre;
    }

    public TreeNode clone(TreeNode root) {
        if (root == null) return null;
        TreeNode newRoot = new TreeNode(root.val);
        newRoot.left = clone(root.left);
        newRoot.right = clone(root.right);
        return newRoot;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}